package java学习.算法.动态规划.暴力递归与动态规划;

/**
 * **************
 * 项目名称: 蓝桥杯 <br/>
 * 文件名称:  <br/>
 * 文件描述: 这里添加您的类文件描述，说明当前文件要包含的功能。 <br/>
 * 文件创建：刘世锦 <br/>
 * 创建时间: 2022/5/16 <br/>
 *
 * @version v1.0 <br/>
 * @update [序号][日期YYYY-MM-DD][更改人姓名][变更描述]<br/>
 * *************
 */
public class 汉诺塔 {
    /**
     * 思路：
     *
     * 1. 先把 1~N-1 的盘 从左移到中间。
     *    - 具体怎么做呢：
     *      1. 将 1~N-2的盘 从左到右
     *      2. 将最后一个N-1 直接从左到中；
     *      3. 之后将1~N-2 的从右到中；依次递归
     * 2. 此时将N 的盘 从左到右。
     * 3. 再将 1~N-1 的盘从中间到右边、
     *    - 与第一大步一样。
     */

    public static void main(String[] args) {
        lefttoRight(3);
fromToOther(3,"left","right","mid");
    }
    public static void lefttoMid(int n){
        if (n==1){
            System.out.println("1步从左到中");
            return;
        }
        lefttoRight(n-1);
        System.out.println(n+"从左到中");
        righttoMid(n-1);

    }

    private static void midtoRight(int n) {
        if (n==1){
            System.out.println("1步从中到右");return;
        }
        midtoLeft(n-1);
        System.out.println(n+"从中到右");
        lefttoRight(n-1);

    }

    private static void midtoLeft(int n) {
        if (n==1){
            System.out.println("1步从中到左");return;
        }
        midtoRight(n-1);
        System.out.println(n+"从中到左");
        righttoLeft(n-1);
    }

    private static void righttoLeft(int n) {
        if (n==1){
            System.out.println("1步从右到左");return;
        }
        righttoMid(n-1);
        System.out.println(n+"从右到左");
        midtoLeft(n-1);
    }

    private static void righttoMid(int n) {
        if (n==1){
            System.out.println("1步从右到中");return;
        }
        righttoLeft(n-1);
        System.out.println(n+"从右到中");
        lefttoMid(n-1);
    }

    private static void lefttoRight(int n) {
        if (n==1){
            System.out.println("1步从左到右");return;
        }
        lefttoMid(n-1);
        System.out.println(n+"从左到右");
        midtoRight(n-1);

    }

    // 进阶版： 抽象出：from to other
    public  static  void fromToOther(int n,String from , String to ,String other){
        if (n==1){
            System.out.println("from  " +from +"   to "+to+" 1");return;
        }
        fromToOther(n-1,from,other,to);
        System.out.println("将"+n+"from  " +from +"   to "+to+"  ");
        fromToOther(n-1,other,to,from);
    }
}
